Fast Fourier Transform (FFT) is a fast method for computing Discrete Fourier Transform (DFT). FFT has many applications in digital signal processing, image processing, holography, spectrum estimation, fast convolution, Orthogonal Frequency Division Multiplexing (OFDM) based modulation and demodulation, etc. An FFT operates by decomposing a length N signal into many smaller length signals and then performing FFT on those smaller length signals. A length N signal is also referred to as an N-point signal herein. The decomposition process is then applied to the smaller length signals. This process is continued until the smallest length signal is reached. In case of a two-way decomposition, the smallest length is two and the particular method of two way decomposition is referred to as radix-2 FFT. If the decomposition is performed into three different smaller length signals, the process is referred to as radix-3 FFT. In general, any radix-r may be used for FFT but some radixes may have certain structural advantages in terms of implementation complexity or speed. At the final stage of decomposition, the Fourier transform of the smallest length signal corresponding to the radix size may be performed explicitly using the basic addition, subtraction, and multiplication operations in a structure commonly referred to as a butterfly. A butterfly may be radix-2, radix-3, etc. FIG. 1 shows examples of radix-2, radix-3 and radix-5 butterfly structures.
The suitability of a particular radix for FFT may depend on the length of the original signal. For example, if the original length N is a power of two such as 64, then FFT using radixes of smaller powers of two such as 2, 4, 8, etc., may offer the best complexity and performance tradeoff. In another example, if the original length N is a power of three such as 81, then FFT using radixes of smaller powers of three such as 3 or 9 may offer the best complexity and performance tradeoff.
In some cases the length N may be a composite number which cannot be represented as a power of a single number. For example, N=30 is a composite number with factors 2, 3, and 5. To perform FFT of signals whose lengths are composite numbers, use of mixed radix FFT structures may be required. For example, a 30-point FFT may be implemented as a cascade of radix-2, followed by radix-3 and finally followed by radix-5 structure. Another method for 30-point FFT may be implemented as a cascade of radix-5, radix-3, and radix-2 structures. In general, any order of the radix structures may be used but depending on the specific value of the original length N a particular order may be beneficial in terms of complexity and performance tradeoffs.
When converting a signal from frequency domain to time domain, the process is referred to as inverse DFT. The process of converting a time domain signal into frequency domain is simply referred to as DFT. In general, the DFT and the inverse DFT processing is identical except for the sign of the exponent of the kernel term. In the present disclosure, the term FFT is used to refer to fast computation of both DFT and inverse DFT.
The FFT algorithm may be implemented either with Decimation-In-Time (DIT) or with Decimation-In-Frequency (DIF) method. Often the FFT computations are done “in-place” where the input memory and the output memory after each butterfly operation is the same. Because of the reduced memory usage, the in-place computation method is preferred for implementation. However, the in-place computation leads to either output signal not in its natural order or requiring the input signal not in its natural order. A signal that is not in its natural order is referred to as a shuffled signal herein. Depending on whether the DIT or DIF method is used, reordering of the input or the output signal may need to be done to get it in the correct natural order. In case of radix-2 FFT the reordering amounts to a simple bit-reversal. For example, in case of an 8-point signal, the index of a data point within a signal may be represented as three bit sequence b0b1b2. The bit reversed index of the same data point may be represented as b2b1b0. The bit-reversal operation may be straightforward to implement with very low complexity in hardware structures but may have non-negligible complexity and delay in software implementations, especially for large N. FIG. 2 shows the natural order and bit reversed order for an 8-point signal when the FFT is performed using three radix-2 stages.
In case of a single radix but non radix-2 implementations, such as radix-3, radix-4, radix-5, etc., the reordering of the shuffled signal may be realized by generalizing the bit-reversal operation to the digit-reversal operation. FIG. 3 shows the natural order and digit reversed order for a 9-point data signal when the FFT is performed using two radix-3 stages.
Mixed radix FFT is an FFT structure that uses a combination of two or more types of radixes. Hence reordering by bit reversing or digit reversing the index is no longer straightforward. Therefore, there is a need for a method for the reordering of a shuffled signal for an FFT structure that uses a combination of two or more types of radixes.
The reordering of a signal in case of mixed radix FFT may depend on the order in which the butterflies are arranged. For example, in case of a 6-point signal the shuffled indices for an FFT structure with radix-2 butterfly followed by a radix-3 butterfly are not the same for an FFT structure with radix-3 butterfly followed by a radix-2 butterfly as shown respectively in FIG. 4 and FIG. 5. Hence, the order in which the butterflies are arranged in an FFT structure also affects the reordering.
In some applications FFT for many different lengths of composite values may need to be computed. A single FFT structure may be desirable to support such variety of lengths. An explicit bit or digit reversal stage at the end of complete FFT may have a non-negligible impact on the complexity and latency. A method and apparatus are disclosed that enable low complexity and zero latency implementation for obtaining correct order signal at the output of the FFT.